Negative base

 ( Non-standard Positional Numeral Systems ) 

A negative base (or negative radix) may be used to construct a non-standard positional numeral system. Like other place-value systems, each position holds multiples of the appropriate power of the system's base; but that base is negative—that is to say, the base is equal to for some natural number ().

Negative-base systems can accommodate all the same numbers as standard place-value systems, but both positive and negative numbers are represented without the use of a minus sign (or, in computer representation, a sign bit); this advantage is countered by an increased complexity of arithmetic operations. The need to store the information normally contained by a negative sign often results in a negative-base number being one digit longer than its positive-base equivalent.

The common names for negative-base positional numeral systems are formed by prefixing nega- to the name of the corresponding positive-base system; for example, negadecimal (base −10) corresponds to decimal (base 10), negabinary (base −2) to binary (base 2), negaternary (base −3) to ternary (base 3), and negaquaternary (base −4) to quaternary (base 4).. Knuth mentions both negabinary and negadecimal.The negaternary system is discussed briefly in

Remark

Negabinary was implemented in the early Poland computer BINEG (and UMC), built 1957–59, based on ideas by Z. Pawlak and A. Lazarkiewicz from the Mathematical Institute in Warsaw. Marczynski, R. W., "The First Seven Years of Polish Computing" , IEEE Annals of the History of Computing, Vol. 2, No 1, January 1980 Implementations since then have been rare.

zfp, a floating-point compression algorithm from the Lawrence Livermore National Laboratory, uses negabinary to store numbers. According to zfp's documentation:

Unlike sign-magnitude representations, the leftmost one-bit in negabinary simultaneously encodes the sign and approximate magnitude of a number. Moreover, unlike two’s complement, numbers small in magnitude have many leading zeros in negabinary regardless of sign, which facilitates encoding.

$a\; =\; \backslash sum\_\{i=0\}^\{n\}d\_\{i\}(-r)^\{i\}$

Negative-base systems may thus be compared to signed-digit representations, such as balanced ternary, where the radix is positive but the digits are taken from a partially negative range. (In the table below the digit of value −1 is written as the single character T.)

Some numbers have the same representation in base as in base . For example, the numbers from 100 to 109 have the same representations in decimal and negadecimal. Similarly,

$17=2^4+2^0=(-2)^4+(-2)^0$

Some numbers with their expansions in a number of positive and corresponding negative bases are:

Note that, with the exception of nega balanced ternary, the base expansions of negative integers have an even number of digits, while the base expansions of the non-negative integers have an odd number of digits.

$-5\; \backslash div\; (-3)\; =\; 2\; ~\backslash mathrm\{remainder\}~\; 1$

For example, to convert 146 in decimal to negaternary:

$\backslash begin\{array\}\{rr\}$

146 \div (-3) = & -48 ~\mathrm{remainder}~ 2 \\
-48 \div (-3) = &  16 ~\mathrm{remainder}~ 0 \\
 16 \div (-3) = &  -5 ~\mathrm{remainder}~ 1 \\
 -5 \div (-3) = &   2 ~\mathrm{remainder}~ 1 \\
  2 \div (-3) = &   0 ~\mathrm{remainder}~ 2
     

Proof: −3 · (−3 · (−3 · (−3 · ( 2 ) + 1 ) + 1 ) + 0 ) + 2 = ((( 2 · (−3) + 1) · (−3) + 1) · (−3) + 0) · (−3) + 2

Proof: 2 + ( 0 + ( 1 + ( 1 + ( 2 ) · −3 ) · −3) · −3 ) · −3 = 146₁₀.

Note that in most programming languages, the result (in integer arithmetic) of dividing a negative number by a negative number is rounded towards 0, usually leaving a negative remainder. In such a case we have . Because , is the positive remainder. Therefore, to get the correct result in such case, computer implementations of the above algorithm should add 1 and to the quotient and remainder respectively.

string result = string.Empty;
     

while (val != 0)
{
	int remainder = val % -2;
	val = val / -2;
     

	if (remainder < 0)
	{
		remainder += 2;
		val += 1;
	}
     

	result = remainder.ToString() + result;
}
     

return result;
     

   std::bitset result;
   std::size_t bit_position = 0;
     

   while (value != 0)
   {
       const auto div_result = std::div(value, -2);
     

       if (div_result.rem < 0)
           value = div_result.quot + 1;
       else
           value = div_result.quot;
     

       result.set(bit_position, div_result.rem != 0);
     

       ++bit_position;
   }
     

   return result;
     

string result = string.Empty;
     

while (val != 0)
{
	int remainder = val % -3;
	val = val / -3;
     

	if (remainder < 0)
	{
		remainder += 3;
		val += 1;
	}
     

	result = remainder.ToString() + result;
}
     

return result;
     

   """Decimal to negaternary"""
   if i == 0:
       digits = ["0"]
   else:
       digits = []
       while i != 0:
           i, remainder = divmod(i, -3)
           if remainder < 0:
               i, remainder = i + 1, remainder + 3
           digits.append(str(remainder))
   return "".join(digits[::-1])
     

 (if (zerop i)
     "0"
     (let ((digits "")
           (rem 0))
       (loop while (not (zerop i)) do
         (progn
           (multiple-value-setq (i rem) (truncate i -3))
           (when (minusp rem)
             (incf i)
             (incf rem 3))
           (setf digits (concatenate 'string (write-to-string rem) digits))))
       digits)))
     

   ArrayList result_rev = new ArrayList<>();
   int number = input;
   while (number != 0) {
       int i = number % base;
       number /= base;
       if (i < 0) {
           i += Math.abs(base);
           number++;
       }
       result_rev.add(i);
   }
   return Collections.reverse(results_rev.clone());
     

   // Would throw exception if base is beyond the 64 possible characters
   return lst.stream().map(n -> alphabet[n]).collect(Collectors.joining(""));
     

 ;; NUM is any number.
 ;; BAZ is any number in the interval [-10, -2]. (This is forced by how we do string notation.)
 ;;
 ;; NUM and BAZ will be truncated to an integer if they're floats (e.g. 14.25
 ;; will be truncated to 14, -123456789.87 to -123456789, etc.).
 (if (and (numberp num)
          (numberp baz)
          (<= (fix baz) -2)
          (> (fix baz) -11))
     (progn
       (setq baz (float (fix baz))
             num (float (fix num))
             dig (if (= num 0) "0" ""))
       (while (/= num 0)
              (setq rst (- num (* baz (setq num (fix (/ num baz))))))
              (if (minusp rst)
                  (setq num (1+ num)
                        rst (- rst baz)))
              (setq dig (strcat (itoa (fix rst)) dig)))
       dig)
     (progn
       (prompt
        (cond
          ((and (not (numberp num))
                (not (numberp baz)))
           "\nWrong number and negabase.")
          ((not (numberp num))
           "\nWrong number.")
          ((not (numberp baz))
           "\nWrong negabase.")
          (t
           "\nNegabase must be inside [-10 -2] interval.")))
       (princ))))
     

1. the input is available in and coded in (base +2; digits in $\backslash \{0,\; 1\backslash \}$) (as in most of today's digital computers),
2. there are add () and xor () operations, which operate on such bitstrings (as in most of today's digital computers),
3. the set $D$ of output digits is standard, i. e. $D\; =\; \backslash \{0,\; |b|-1\backslash \}$ with base $b\backslash in\; \backslash \{-2,-4\backslash \}$,
4. the output is coded in the same bitstring format, but the meaning of the places is another one.

uint32_t Schroeppel2 = 0xAAAAAAAA; // = 2/3*((2*2)^16-1) = ...1010
return (value + Schroeppel2) ^ Schroeppel2; // eXclusive OR
// resulting unsigned int to be interpreted as string of elements ε {0,1} (bits)
     

JavaScript port for the same shortcut calculation: function toNegaBinary(value) {

   const Schroeppel2 = 0xAAAAAAAA;
   // Convert as in C, then convert to a NegaBinary String
   return ( ( value + Schroeppel2 ) ^ Schroeppel2 ).toString(2);
     

The algorithm is first described by Schroeppel in the HAKMEM (1972) as item 128. The Wolfram MathWorld documents a version in the Wolfram Language by D. Librik (Szudzik).See the MathWorld Negabinary link. Specifically, the references are:

• Szudzik, M. "Programming Challenge: A Mathematica Programming Contest". Wolfram Technology Conference, 1999.
• Schroeppel, R. Item 128 in Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, p. 24, Feb. 1972. http://www.hakmem.org/#item128

uint32_t Schroeppel4 = 0xCCCCCCCC; // = 4/5*((2*4)^8-1) = ...11001100 = ...3030
return (value + Schroeppel4) ^ Schroeppel4; // eXclusive OR
// resulting unsigned int to be interpreted as string of elements ε {0,1,2,3} (pairs of bits)
     

JavaScript port for the same shortcut calculation: function toNegaQuaternary(value) {

   const Schroeppel4 = 0xCCCCCCCC;
   // Convert as in C, then convert to NegaQuaternary String
   return ( ( value + Schroeppel4 ) ^ Schroeppel4 ).toString(4);
     

The second row of this table, for instance, expresses the fact that −1 = 1 + 1 × −2; the fifth row says 2 = 0 + −1 × −2; etc.

As an example, to add 1010101 (1 + 4 + 16 + 64 = 85) and 1110100 (4 + 16 − 32 + 64 = 52),

Carry:          1 −1  0 −1  1 −1  0  0  0
First addend:         1  0  1  0  1  0  1
Second addend:        1  1  1  0  1  0  0 +
               --------------------------
Number:         1 −1  2  0  3 −1  2  0  1
Bit (result):   1  1  0  0  1  1  0  0  1
Carry:          0  1 −1  0 −1  1 −1  0  0
     

so the result is 110011001 (1 − 8 + 16 − 128 + 256 = 137).

Extra carry:    1  1  1  0  1  0  0  0
Carry:             0  1  1  0  1  0  0  0
First addend:         1  0  1  0  1  0  1
Second addend:        1  1  1  0  1  0  0 +
               --------------------------
Answer:         1  1  0  0  1  1  0  0  1
     

$s\_i\; =\; a\_i\; \backslash oplus\; b\_i\; \backslash oplus\; c\_i^+\; \backslash oplus\; c\_i^-$

$c\_\{i+1\}^+\; =\; \backslash overline\{a\_i\}\backslash overline\{b\_i\}\backslash overline\{c\_i^+\}c\_i^-$

$c\_\{i+1\}^-\; =\; a\_i\; b\_i\; \backslash overline\{c\_i^-\}\; +\; (a\_i\; \backslash oplus\; b\_i)c\_i^+\; \backslash overline\{c\_i^-\}$

$2x\; \backslash oplus\; ((2x\; \backslash oplus\; x)\; +\; 1)$

As an example, to compute 1101001 (1 − 8 − 32 + 64 = 25) minus 1110100 (4 + 16 − 32 + 64 = 52),

Carry:          0  1 −1  1  0  0  0
First number:   1  1  0  1  0  0  1
Second number: −1 −1 −1  0 −1  0  0 +
               --------------------
Number:         0  1 −2  2 −1  0  1
Bit (result):   0  1  0  0  1  0  1
Carry:          0  0  1 −1  1  0  0
     

so the result is 100101 (1 + 4 −32 = −27).

Unary negation, , can be computed as binary subtraction from zero, .

To multiply, multiply like normal decimal or binary numbers, but using the negabinary rules for adding the carry, when adding the numbers.

First number:                   1  1  1  0  1  1  0
Second number:                  1  0  1  1  0  1  1 ×
              -------------------------------------
                                1  1  1  0  1  1  0
                             1  1  1  0  1  1  0
     

                       1  1  1  0  1  1  0
                    1  1  1  0  1  1  0
     

              1  1  1  0  1  1  0                   +
              -------------------------------------
Carry:        0 −1  0 −1 −1 −1 −1 −1  0 −1  0  0
Number:       1  0  2  1  2  2  2  3  2  0  2  1  0
Bit (result): 1  0  0  1  0  0  0  1  0  0  0  1  0
Carry:           0 −1  0 −1 −1 −1 −1 −1  0 −1  0  0
     

For each column, add carry to number, and divide the sum by −2, to get the new carry, and the resulting bit as the remainder.

As with positive-base systems, terminating representations correspond to fractions where the denominator is a power of the base; repeating representations correspond to other rationals, and for the same reason.

$T:=0.\backslash overline\{01\}\_b\; =\; \backslash sum\_\{i=1\}^\{\backslash infty\}\; b^\{-2i\}\; =\; \backslash frac1\{b^2-1\}\; =\; \backslash frac1\{r^2-1\}$

$0.\backslash overline\{0\backslash mathbf\{t\}\}\_b=\backslash mathbf\{t\}T=\backslash frac\{r\backslash !-\backslash !\backslash !1\}\{r^2-1\}=\backslash frac1\{r+1\}$     as well as

$1.\backslash overline\{\backslash mathbf\{t\}0\}\_b\; =\; 1+\backslash mathbf\{t\}bT\; =\; \backslash frac\{(r^2-1)+(r\backslash !-\backslash !\backslash !1)b\}\{r^2-1\}=\; \backslash frac1\{r+1\}.$

For example, in negaternary, i.e. $b=-3$ and $\backslash mathbf\{t\}=2$, there is

$1.\backslash overline\{02\}\_\{(-3)\}\; =\; \backslash frac\{5\}\{4\}\; =\; 2.\backslash overline\{20\}\_\{(-3)\}$.

Such non-unique representations can be found by considering the largest and smallest possible representations with integer parts 0 and 1 respectively, and then noting that they are equal. (Indeed, this works with any integer-base system.) The rationals thus non-uniquely expressible are those of form

$\backslash frac\{z(r+1)\; +\; 1\}\{b^i(r\; +\; 1)\}$

• Quater-imaginary base
• Binary
• Balanced ternary
• Quaternary numeral system
• 1 − 2 + 4 − 8 + ⋯ (p-adic numbers)

• Henry S. Warren Jr. (2025). 9780321842688, Addison Wesley – Pearson Education, Inc.. ISBN 9780321842688